package test1;

import java.util.*;

public class TestHeap {
    public int[] elem;
    public int usedSize;
    public TestHeap(){
        this.elem=new int[10];
    }

    //parent: 每颗树的根节点    len：每棵树的调整的结束位置
    public void shiftDown(int parent,int len){
        int child=2*parent + 1;
        while(child < len){
            if(child+1 < len && elem[child] < elem[child+1]) {
                child++;
            }
            if(elem[child] > elem[parent]){
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                parent=child;
                child=2*parent + 1;
            }else{
                break;
            }
        }


    }

    public void createBigHeap(int[] array){
        for(int i=0;i<array.length;i++){
            elem[i]=array[i];
            usedSize++;
        }
        //此处不能用parent=(数组长度-1)/2,假设数组长度为10，但是只存放了5 个元素
        for(int parent=(usedSize-1-1)/2;parent>=0;parent--) {
            //调整
            shiftDown(parent,usedSize);
        }
    }


    public void offer(int val){
        if(isFull()){
            //扩容
            elem=Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize]=val;
        usedSize++;
        shiftUp(usedSize-1);
    }
    public void shiftUp(int child){
        int parent=(child-1)/2;
        while(child>0){
            if(elem[child] >elem[parent]) {
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                child=parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }

    }
    public boolean isFull(){
        return usedSize==elem.length;
    }

    public int poll(){
        if(isEmpty()){
            throw new RuntimeException("优先级队列为空");
        }
        int tmp=elem[0];
        elem[0]=elem[usedSize-1];
        elem[usedSize-1]=tmp;
        usedSize--;
        shiftDown(0,usedSize);
        return tmp;
    }
    public boolean isEmpty(){
        return usedSize==0;
    }

    //堆排序
    public void heapSort(){
        int end=usedSize-1;
        while(end > 0){
            int tmp=elem[0];
            elem[0]=elem[end];
            elem[end]=tmp;
            shiftDown(0,end);
            end--;

        }

    }

    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> maxHeap=new PriorityQueue<>(k, new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return (o2.get(0)+o2.get(1))-(o1.get(0)+o1.get(1));
            }
        });
        for(int i=0;i<nums1.length;i++){
            for(int j=0;j<nums2.length;j++){
                if(maxHeap.size()<k){
                    List<Integer> list=new ArrayList<>();
                    list.add(nums1[i]);
                    list.add(nums2[j]);
                    maxHeap.offer(list);
                }else{
                    int top=maxHeap.peek().get(0)+maxHeap.peek().get(1);
                    if(nums1[i]+nums2[j] < top){
                        List<Integer> list=new ArrayList<>();
                        maxHeap.poll();
                        list.add(nums1[i]);
                        list.add(nums2[j]);
                        maxHeap.offer(list);
                    }
                }
            }

        }
        List<List<Integer>> ret=new ArrayList<>();
        for(int i=0;i<k && !maxHeap.isEmpty();i++){
            ret.add(maxHeap.poll());
        }
        return ret;


    }


}
